NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/5433

Internet Message Format | 1996-08-05 | 6.2 KB

Path: mail2news.demon.co.uk!wildcard.demon.co.uk
From: Cyber Surfer <[e-mail]>
Newsgroups: comp.lang.lisp,comp.lang.c++,comp.lang.c,comp.lang.misc
Subject: Re: GC & traditional allocators & textbooks
Date: Sun, 04 Feb 96 17:40:23 GMT
Organization: The Wildcard Killer Butterfly Breeding Ground
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <4eu5l9$[e-mail]> <[e-mail]> <4f2ila$[e-mail]>
Reply-To: [e-mail]
X-NNTP-Posting-Host: wildcard.demon.co.uk
X-Newsreader: Demon Internet Simple News v1.30
X-Mail2News-Path: wildcard.demon.co.uk

In article <4f2ila$[e-mail]>
           [e-mail] "Paul Wilson" writes:

> >> >If you want to know about basic
> >> >garbage collecting, I'd recommend a computer science book, as it'll
> >> >probably be more up to date.
> >>
> >> I have to disagree here.  I know of no textbooks with even a decent
> >> discussion of garbage collection. [...]
> >
> >Was I refering to modern GC? I'm not sure. I don't know of any books
> >on modern GC, but a book 20 years old seems to contain GC techniques
> >that many C/C++ programmers are unaware of. Even if that's the best
> >book on the subject, it could still enlighten a few programmers.
>
> OK, agreed.  There are some fundamental algorithms that *are* in some
> textbooks and should be better known.

I agree. I just suspect that those who think about these issues a lot
under estimate how a programmer who is unfamiliar with even basic GC
will react to the more advanced techniques. Disbelief is a common
reaction, which I'm sure you've also seen. Arthur C Clarke's third
law is worth quoting here, "Any sufficiently advanced technology is
indistingishable from magic". Confront a programmer with some "magic"
and they'll disbelieve it.

> On the other hand, even some of the textbooks that do discuss the
> fundamental algorithms often propagate naive views about GC that are rather
> damaging.  (Henry Baker, Hans Boehm, and I have all put a fair amount
> of effort into trying to slow the spread of those myths on the net.)

And I hope you have a lot of success in your efforts, some of which I've
witnessed here on UseNet. However, you first have to kill the idea that
"successful GC" is magic. If it does work, then you'll have to offer
examples of "real world" uses of GC before a typical programmer will be
convinced. Most of the programmers I know are very suspicious of computer
science, which doesn't help. There's no way they'll ever bother reading
a paper about GC. On the other hand, they probably won't have read any
books on the subject, either.

This only leaves the word of other programmers, and the masses of code
that apparently has been written _without_ the use of GC. As I've said,
C/C++ programers see the cost of everything and the value of nothing.
Please note that I'm also a C/C++ programmers myself, and I also make
that mistake from time to time. Some languages let you focus on the
very small picture, instead of the big picture, where GC can help.

> This is also true of traditional allocators.  The history of allocator
> research has been a big mess---the literature is a bit of a disaster
> area---and the textbooks reflect this.  The analyses in the books are
> shallow and largely wrong.  (This is less attributable to the textbooks
> authors than the weak discussions of GC.  It's not their fault that they
> can't summarize the gist of the literature and get it right, because
> the literature in general is disorganized, inconsistent, and often wrong.)

I won't argue with that! ;-) I'd love to see a good summary.

> One of the problems in the area of traditional memory allocators is that
> people have taken one particular textbook far too seriously---Volume 1
> of Knuth's _The_Art_of_Computer_Programming_.  It was written in 1968,
> and some of it has turned out to be less than helpful.  It's still the
> standard reference, though, and other textbook writers often regurgitate
> its discussion of memory allocators.  Implementors often look at it and
> go and implement things that have been known to be bad since the early
> 1970's.  (Knuth is still tremendously influential in allocator work,
> despite the fact that he doesn't appear to have written anything about it
> in over 25 years.  This is not Knuth's fault, of course---inertia makes
> the world go 'round.)

I also have that book, and the other 3 volumes. However, they didn't
stop me from writting and using a GC. If I wanted to write a floating
point package (very unlikely, even 10 years ago), then I might turn
to Knuth, but not for anything like memory management.

Perhaps I've been brainwashed by those evil people are Xerox PARC,
when I read the August 1981 issue of Byte. ;-) I doubt it. I just
don't have a blind spot that prevents me from seeing problems for
which a GC can help. As you said, Knuth's book is very old. In it
he refers to decimal computers! <ahem> Very dated, now.

> "Modified First Fit" with the roving pointer is the clearest example.  It
> was a bad idea, and it was quickly shown to be bad, but some other textbook
> writers keep mindlessly cribbing from Knuth, and even some implementors still
> use it.

Is it really worse than Best Fit? I've wondered about that ever
since first read that book. You seem like a good person to ask. ;)

> Obligatory positive comment:  the best textbook discussion of allocators
> that I know of is Tim Standish's in _Data_Structure_Techniques_.  He doesn't
> recognize the near-universal methodological problems with allocator studies,
> but he's unique in recognizing the basic data structure and algorithm issues
> in implementing allocators.

I'll see if I can find that book. Thanks.

> This site also has our big survey on memory allocators from IWMM '95, which
> I hope will influence future textbooks.  It talks about empirical methodology
> as well as giving a fairly exhaustive treatment of implementation techniques.

I FTP'd it a week or two ago. I intend to read it, as soon as I
get a (binary) copy of Ghostscript for NT. Thanks.
--
<URL:http://www.demon.co.uk/community/index.html>
<URL:http://www.enrapture.com/cybes/namaste.html>
Po-Yeh-Pao-Lo-Mi | "You can never browse enough."